package leetcode.双指针法;

/**
 * 删除链表的倒数第N个节点
 *
 * 双指针法：两个指针之间间隔 N 个节点即可
 */
public class Test19删除链表的倒数第N个节点 {

    static class ListNode {

        int val;

        ListNode next;

        ListNode(int x) {
            val = x;
        }

    }

    public static ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode l = head;
        ListNode beforeCurrentNode = head;
        // 先遍历一遍求出链表长度
        int length = 0;
        while (l != null) {
            length++;
            l = l.next;
        }
        l = head;
        // 然后根据链表长度 length - n 得到需要删除的节点位置，再删除
        for (int i = 0; i < length - n; i++) {
            beforeCurrentNode = l;
            l = l.next;
        }
        // 断开链表的方式很简单，直接往后多遍历一次，然后将此时的链表索引值连接到遍历前的链表上
        beforeCurrentNode.next = l.next;
        return head;
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
        ListNode q = dummy;
        // q 先移动到 n+1 处
        for (int i = 0; i < n+1; i++) {
            q = q.next;
        }
        while (q != null) {
            p = p.next;
            q = q.next;
        }
        // 开始清空第 N 个节点
        ListNode delNode = p.next;
        p.next = delNode.next;
        delNode = null;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(2);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(5);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        removeNthFromEnd(l1, 2);
        while (l1 != null) {
            System.out.print(l1.val);
            l1 = l1.next;
        }
    }
}
